package com.laotang.第_4_章_哈希表.力扣_383_赎金信;


import java.util.HashMap;
import java.util.Map;

public class _383_ransom_note {

    // 时间复杂度：O(m + n)
    // 空间复杂度：O(n)
    public boolean canConstruct1(String ransomNote, String magazine) {
        Map<Character, Integer> cnt = new HashMap<>();
        for (char c : magazine.toCharArray()) {
            if (cnt.containsKey(c)) {
                cnt.put(c, cnt.get(c) + 1);
            } else {
                cnt.put(c, 1);
            }
        }

        for (char c : ransomNote.toCharArray()) {
            if (!cnt.containsKey(c)) return false;
            int remain = cnt.get(c) - 1;
            if (remain < 0) return false;
            cnt.put(c, remain);
        }

        return true;
    }

    // 数组代替 Map
    // 时间复杂度：O(m + n)
    // 空间复杂度：O(1)
    public boolean canConstruct2(String ransomNote, String magazine) {
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }

        for (char c : ransomNote.toCharArray()) {
            if (cnt[c - 'a'] == 0) return false;
            cnt[c - 'a']--;
        }

        return true;
    }
}
